package main

import (
	"sort"
)

func searchMatrix(matrix [][]int, target int) bool {
	pivot := sort.Search(len(matrix[0]), func(i int) bool {
		return matrix[0][i] > target
	}) 
	for j := 0; j < pivot; j++ {
		result := sort.Search(len(matrix), func(i int) bool {
			return matrix[i][j] >= target
		})
		if result < len(matrix) && matrix[result][j] == target {
			return true
		}
	}
	return false
}

func main() {
	mat := [][]int {
		{1, 4, 7, 11},
		{2, 5, 8, 12},
		{4, 6, 9, 16},
	}
	println(searchMatrix(mat, 5))
}